/*
 * @lc app=leetcode.cn id=148 lang=golang
 *
 * [148] 排序链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func sortList(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	first, second := split1(head)
	if first == nil || second == nil {
		return merge(first, second)
	}

	return merge(sortList(first), sortList(second))

}

func split1(head *ListNode) (*ListNode, *ListNode) {
	if head == nil {
		return nil, nil
	}
	if head.Next == nil {
		return head, nil
	}
	slow, fast := &ListNode{Next: head}, head
	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
	}
	tail := slow.Next
	slow.Next = nil

	return head, tail
}

func merge(l1, l2 *ListNode) *ListNode {
	node := &ListNode{}
	ptr := node
	for l1 != nil && l2 != nil {
		if l1.Val < l2.Val {
			ptr.Next = l1
			l1 = l1.Next
		} else {
			ptr.Next = l2
			l2 = l2.Next
		}
		ptr = ptr.Next
	}
	if l1 == nil {
		l1 = l2
	}
	for l1 != nil {
		ptr.Next = l1
		l1 = l1.Next

		ptr = ptr.Next
	}
	return node.Next
}

// @lc code=end

